Various related art has been proposed pertaining to navigation devices that are installed in a probe car, collect probe information, and transmit the probe information to an information distribution center. For example, a road link number that specifies the road class (expressway, general road, etc.) of a link along a past travel route of a vehicle, a link travel time, a travel speed, and the like are successively accumulated and stored for a road link (referred to as a “link” below) that is shown using road map data. There is a car navigation device constituted so as to compare a pre-stored average travel speed of the link and a real-time average travel speed of the link. Only in cases where there is a predetermined difference does the car navigation device transmit probe information such as the road link number, the link travel time, and the travel speed collected at the link to a control center (see Japanese Patent Application Publication No. JP-A-2007-264731, paragraphs 0014 to 0049 and FIGS. 1 to 4, for example).